Карты Карно

**Карта Карно функции $f$** — это специальная запись таблицы значений $f$: * карта — это прямоугольная таблица из $2^{k}$ клеток, где $k$ — арность $f$ * строки и столбцы проиндексированы так, что каждой клетке однозначно соответствует набор значений переменных, в клетке пишется значение функции (обычно пишут только единицы)

Кратчайшую ДНФ строят, покрывая все клетки с единицами прямоугольниками такими, что * число клеток в прямоугольнике — степень двойки * если клеток $2^{i}$, то $k-i$ переменных принимают в этих клетках одно значение (определяют элементарную конъюнкцию), а остальные $i$ — все наборы значений

!karno-example.png